#include "huffman_tree.h"

//存储所有huffman编码的数组
HuffmanCode* hcode;
//记录huffman编码的下标 和string.h的index冲突因此加下划线
size_t _index = 0;

// static char code[] = "abcdefg ";
// static int weight[] = {1,2,3,4,5,6,7,9};
static char _code[256] = {};
static int _size = 0;
static int _weight[256] = {};

//根据权重进行比较
static int cmp(const void* p1, const void* p2) {
    const TreeNode* n1 = p1;
    const TreeNode* n2 = p2;
    return (n1->weight - n2->weight) % 2;
}

TreeNode* create_huffman_t() {

    // size_t len = strlen(code);
    //创建一个小根堆
    Heap* heap = create_ht(_size);
    //设置比较函数
    set_cmp_ht(heap, cmp);
    //创建森林
    for (int i = 0; i < _size; i++) {
        //根据字符和权重创建节点并加入小根堆
        push_ht(heap, create_tn(&_code[i], _weight[(int)_code[i]]));
    }
    while (true) {
        //从堆中获取前两个权重最小的节点 获取后珊瑚粗
        TreeNode* left = top_ht(heap);
        pop_ht(heap);
        TreeNode* right = top_ht(heap);
        pop_ht(heap);
        //根据左右子树的权重创建父节点
        TreeNode* root = create_tn(NULL, left->weight + right->weight);
        //创建后连接左右子树
        root->left = left;
        root->right = right;
        //如果堆空了 说明huffman树已经创建完成
        if (empty_ht(heap))
            return root;
        //如果没有结束 需要把生成的节点加入堆再继续创建
        push_ht(heap, root);
    }
}

void set_weight_file_huffman_t(char* path) {
    FILE* frp = fopen(path, "r+");
    if (!frp)
        return;
    char tmp = 0;
    while (0 < fread(&tmp, 1, 1, frp)) {
        _weight[(int)tmp]++;
    }
    for (int i = 0; i < 256; i++) {
        if (_weight[i] > 0) {
            _code[_size++] = i;
        }
    }
    printf("%d\n", _size);
}

//生成huffman编码 从根节点访问字符的路径
void code_huffman_t(TreeNode* node, int bits, int len) {
    if (NULL == node)
        return;
    //记录当前层 并给下一层预留位置
    int newBits = bits << 1;
    // newBits+=0;
    code_huffman_t(node->left, newBits, len + 1);
    //如果这个节点是要需要编码的字符 叶子节点 记录这个字符以及到这个字符的路径
    //即为huffman编码
    if (node->data) {
        //记录要编码的字符
        hcode[_index].code = *(char*)node->data;
        //记录根节点到当前节点的路径
        hcode[_index].bits = bits;
        //记录huffman编码的位数
        hcode[_index++].cnt = len;
        // printf("asc:%d\t%d\t%d\n",*(char*)node->data,bits,len);
    }
    //记录右子树的路径
    newBits += 1;
    code_huffman_t(node->right, newBits, len + 1);
}

void zip_file(char* inpath, char* outpath) {
    if (!hcode) {
        // hcode = malloc(sizeof(HuffmanCode)*strlen(code));
        hcode = malloc(sizeof(HuffmanCode) * _size);
        code_huffman_t(create_huffman_t(), 0, 0);
    }
    FILE* frp = fopen(inpath, "r+");
    FILE* fwp = fopen(outpath, "w+");
    if (!fwp || !frp)
        return;
    Data data = { 0, 0 };
    char tmp = 0;
    while (0 < fread(&tmp, sizeof(char), 1, frp)) {
        int p = 0;
        while (p < _size && hcode[p].code != tmp)
            p++;
        //如果遍历后发现没有这个字符 那么跳过
        if (p > _size)
            continue;
        // printf("%c",hcode[p].code);
        if (data.cnt + hcode[p].cnt > 64) {
            // printf("%lld %d\n",data.bits,data.cnt);
            fwrite(&data, sizeof(Data), 1, fwp);
            data.bits = 0;
            data.cnt = 0;
        }
        data.bits <<= hcode[p].cnt;
        data.bits += hcode[p].bits;
        data.cnt += hcode[p].cnt;
        // printf("%lld %d\n",data.bits,data.cnt);
    }
    if (data.cnt > 0) {
        // printf("%lld %d\n",data.bits,data.cnt);
        fwrite(&data, sizeof(Data), 1, fwp);
    }
    fclose(frp);
    fclose(fwp);
}

void unzip_file(char* inpath, char* outpath) {
    TreeNode* root = create_huffman_t();
    FILE* frp = fopen(inpath, "r+");
    FILE* fwp = fopen(outpath, "w+");
    if (!frp || !fwp)
        return;
    Data data = { 0, 0 };
    while (0 < fread(&data, sizeof(Data), 1, frp)) {
        TreeNode* node = root;
        for (int i = 1; i <= data.cnt; i++) {
            if (1 & (data.bits >> (data.cnt - i))) {
                node = node->right;
            }
            else {
                node = node->left;
            }
            if (node->data) {
                fwrite(node->data, sizeof(char), 1, fwp);
                node = root;
            }
        }
    }
    fclose(frp);
    fclose(fwp);
}
